package leetcode;

/**
 * Created by tiang on 2018/9/2.
 * Say you have an array for which the ith element is the price of a given stock on day i.
 Design an algorithm to find the maximum profit. You may complete at most k transactions.
 Note:
 You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
 Example 1:
 Input: [2,4,1], k = 2
 Output: 2
 Explanation: Buy on day 1 (price = 2) and sell on day 2 (price = 4), profit = 4-2 = 2.
 Example 2:
 Input: [3,2,6,5,0,3], k = 2
 Output: 7
 Explanation: Buy on day 2 (price = 2) and sell on day 3 (price = 6), profit = 6-2 = 4.
 Then buy on day 5 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3.

 */
public class SellStock {
    /**
     * 如果k>len的话说明每一天都可以买卖，那直接求整个数组的最大收益即可
     * 如果不是的话计算每一段买卖一次的最大收益, dp[i,j]表示i到j买卖一次的最大收益
     * R[i,k]表示，从0~i买卖k次的最大收益
     * R[i,k] = max(R[1,k-1]+dp[1,i],
     *              R[2,k-1]+dp[2,i],
     *              ...
     *              R[i-1,k-1],dp[i-1,i]
     *              )
     * 时间复杂度是o(n2*k)
     * 空间复杂度是O(k*len)
     *
     * ** 勉强能通过。。
     * @param k 买卖k次
     * @param prices 每天股票价格0
     * @return 最大收益
     */
    public int maxProfit(int k, int[] prices) {
        int len = prices.length;
        // 每天都有买卖机会的话，就直接求最大收益
        if(k>=len)
            return maxProfitSub(prices);
        /**
         * 表示从i到j买卖一支情况下的最大收入
         */
        int[][] dp = new int[len][len];
        for(int i=0;i<len;i++){
            // 股票的最低价格
            int min = prices[i];
            for(int j=i+1;j<len;j++){
                // 如果比最低价格大，那么计算当前价值卖出是否是最大收益
                if(prices[j]>min){
                    dp[i][j] = Integer.max(dp[i][j-1], prices[j]-min);
                }else{
                    // 如果比最低价格还小，那么更新最低价格，当前最大收益等于前一天的最大收益
                    min = prices[j];
                    dp[i][j] = dp[i][j-1];
                }
            }
        }
        return maxProfitSub(k, dp, 0, new int[k>len?len+1:k+1][len+1]);
    }

    /**
     * 计算从index天开始，完成k次交易的最大收益
     * @param k 交易次数
     * @param dp 每段时间段交易的最大收益
     * @param index 起始位置
     * @param temp 存储以前计算过的，index天开始交易k次的最大收益
     * @return 最大收益
     */
    private int maxProfitSub(int k, int[][] dp, int index, int[][] temp){
        // 时间已经到最后一天了，或者交易次数已经用完了，返回0
        if(index >= dp.length || k <= 0)
            return 0;
        // 如果以前计算过，那么直接返回
        if(temp[k][index]!=0)
            return temp[k][index];
        int max = 0;
        // 计算R[index,k]
        for(int i=index+1;i<dp.length;i++){
            int value = dp[index][i]+maxProfitSub(k-1, dp, i+1, temp);
            if(value>max)
                max = value;
        }
        temp[k][index] = max;
        return max;
    }

    /**
     * 计算整体的最大收益，即每天都可以买卖的最大收益
     * @param prices 价格
     * @return 最大收益
     */
    private int maxProfitSub(int[] prices) {
        int sum = 0;
        // 实际就是前一天价格比昨天大时就计算收益
        for(int i=1;i<prices.length;i++){
            if(prices[i]>prices[i-1]){
                sum += prices[i]-prices[i-1];
            }
        }
        return sum;
    }
}
